Next: Justification Up: Dijkstra's algorithm Previous: Initialisation Index
The
iterative step of the algorithm is now as follows:
While
is not
empty:
- D1:
- pick any
such that
for all
;
- D2:
- extend
to
;
- D3:
- redefine the function
on
as follows:
- (a)
- if
, leave
unchanged;
- (b)
- otherwise, if
is not adjacent to
, leave
unchanged;
- (c)
- otherwise, if
was not previously defined, set
equal to the sum of
and the length of the
shortest arc from
to
;
- (d)
- otherwise, set
to be the smaller of the old value of
and the sum of
and the length of the shortest arc from
to
.
Peter Williams 2002-06-07